import graph.graph as gt
import math

def adjacentlist(V, E):     #构建领接表
    Ea = []
    for w in V:
        e0 = [w]
        e1 = []
        for (u, v) in E:
            if u == w and (v not in e1):
                e1 = e1 + [v]
            if v == w and (u not in e1):
                e1 = e1 + [u]
        e0 = e0 + [sorted(e1)]
        Ea = Ea + [e0]
    return sorted(Ea)

def tourpath0(V, E, path, m):   #构建哈密顿第一步
    while (len(path) < m):
        w = path[-1]
        i = V.index(w)
        E1 = E[i]
        E2 = E1[1]
        for u in E2:
            if (u not in path):
                path.append(u)
                break
        if path[-1] == w:
            break
    return path

def tourpath1(V, E, path, m):   #构建哈密顿第二步
    v = path.pop()
    while (len(path) != 0):
        u = path[-1]
        i = V.index(u)
        E1 = E[i]
        E2 = E1[1]
        k = E2.index(v)
        while (k < (len(E2) - 1)):
            k = k + 1
            v = E2[k]
            if (v not in path):
                path.append(v)
                break
        if (u != path[-1]):
            break
        v = path.pop()
    return path

def tourpath(V, E, path, m):    #构建哈密顿图第三步
    if (len(path) == m):
        path = tourpath1(V, E, path, m)
    while (len(path) != 0):
        path = tourpath0(V, E, path, m)
        if (len(path) == m):
            break
        path = tourpath1(V, E, path, m)
    return path

def Hamitonpath(V, E, v0):      #构建哈密顿图
    global Ea, paths
    V = sorted(V)
    Ea = adjacentlist(V, E)
    paths = set({})
    path = [v0]
    m = len(V)
    path = tourpath(V, Ea, path, m)
    paths = paths | {tuple(path)}
    while (len(path) == m):
        path = tourpath(V, Ea, path, m)
        if (len(path) == m):
            paths = paths | {tuple(path)}
            # print(path)
    return paths

def shortpath(V, E, di, Hx, path, zn):  #寻找短路径
    V = sorted(V)
    Pm = []
    for p in path:
        vn = p[-1]
        if vn == zn:
            Pm = Pm + [p]
            continue
        # if di[V.index(vn)] != 0:
        #     Pm = Pm + [p]
        #     continue
        for (w, u, v) in E:
            if u == vn:
                kv = V.index(v)
                if di[kv] > 0:
                    di[kv] = di[kv] - 1
                vw = p[0] + w
                if vw < Hx[kv]:
                    Hx[kv] = vw
                    e = [vw] + p[1:] + [v]
                    Pm = Pm + [e]
    return [di, Hx, Pm]

def shortestpath(V, E, v0, vn):     #寻找最短路径
    V = sorted(V)
    [d, di, do] = gt.degreesetw(V, E)
    Pm0 = []
    Pm = [[0, v0]]
    inf = 10000
    Hx = [inf for x in range(len(V))]
    Hx[0] = 0
    while Pm0 != Pm:
        Pm0 = Pm
        [di, Hx, Pm] = shortpath(V, E, di, Hx, Pm0, vn)
    Pm = sorted(Pm)
    return [Hx, Pm[0]]

def Huffmantree(W):             #构建霍夫曼树
    W0 = []
    for [a, w] in W:
        W0 = W0 + [[w, a]]
    tree = sorted(W0)
    while len(tree) != 1:
        w = tree[0][0] + tree[1][0]
        w = math.floor(w * 10000) / 10000
        tree = [[w, tree[0], tree[1]]] + tree[2:]
        tree = sorted(tree)
    return tree[0]

def huffmancoding(subtree, code):   #构建霍夫曼子树编码
    if len(subtree) == 2:
        return [[subtree[1], code]]
    else:
        node0 = subtree[1]
        node1 = subtree[2]
        code = huffmancoding(node0, code + '0') + huffmancoding(node1, code + '1')
        return code

def HuffmanCoding(tree):        #构建霍夫曼编码
    code0 = huffmancoding(tree[1], '0')
    code1 = huffmancoding(tree[2], '1')
    return code0 + code1